//递归版本二叉搜索树
#pragma once 
#include<iostream>
#include<vector>
using namespace std;

template<class K,class V>
struct BSTNode
{
  BSTNode<K,V>* left;
  BSTNode<K,V>* right;
  pair<K,V> _kv;
  BSTNode(const pair<K,V>& kv)
    :_kv(kv),left(nullptr),right(nullptr)
  {}
};

template<class K,class V>
class BSTree
{
public:
  typedef BSTNode<K,V> Node;
  BSTree()
    :root(nullptr)
  {}
  ~BSTree()
  {}
  Node* find(const K& key)
  {
    return _find(root,key);
  }
  bool insert(const pair<K,V>& kv)
  {
    return _insert(root,kv);
  }
  bool erase(const K& key)
  {
    return _erase(root,key);
  }
  K& GetRootVal()
    {
        return root->_kv.first;
    }
    void inorder()
    {
        _inorder(root);
        cout << endl;
    }
    void _inorder(Node* root)
    {
        if(root == nullptr)
            return ;
        _inorder(root->left);
        cout << root->_kv.first<<" ";
        _inorder(root->right);
    }
private:
  bool _erase(Node*& root,const K& key)
  {
    if(root == nullptr)
      return false;
    if(root->_kv.first > key)
      return _erase(root->left,key);
    else if(root->_kv.first < key)
      return _erase(root->right,key);
    else 
    {
       Node* del = nullptr;
       if(root->left == nullptr)
       {
          del = root;
          root = root->right;
       }
       else if(root->right == nullptr)
       {
          del = root;
          root = root->left;
       }
       else
       {
         Node* min = root->left;
         while(min->right)
         {
            min = min->right;
         }
         swap(min->_kv,root->_kv);
         return _erase(root->left,key);
       }
       delete del;
       return true;
    }
  }
  bool _insert(Node*& root,const pair<K,V>& kv)
  {
    if(root == nullptr)
    {
      root = new Node(kv);
      return true;
    }
    if(root->_kv.first > kv.first)
      return _insert(root->left,kv);
    else if(root->_kv.first < kv.first)
      return _insert(root->right,kv);
    else
      return false;
  }
  Node* _find(Node*& root,const K& key)
  {
    if(root == nullptr)
      return root;
    
    if(root->_kv.first > key)
      return _find(root->left,key);
    else if(root->_kv.first < key)
      return _find(root->right,key);
    else
      return root;
  }
private:
  Node* root;
};
